package org.example.sort;

/**
 * <p>
 * Description: 快排
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/14 17:44
 */
public class QuickSort {
    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        int[] nums = {3,30,34,5,9};
//        String result = q.minNumber(nums);
//        System.out.println(result);
        q.quickSort1(nums,0,nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }

    }


    public String minNumber(int[] nums){
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs){
            res.append(s+" ");
        }
        return res.toString();
    }

    /**
     * 字符串拼接比较大小
     * @param strs
     * @param l
     * @param r
     */
    public void quickSort(String[] strs,int l ,int r){
       if(l >= r){
           return;
       }
       int i = l, j = r;
       String tmp = strs[i];

       while (i < j){
           //先从右指针开始比对
           while ((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j){
               j--;
           }
           while ((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j){
               i++;
           }
           //不满足条件， i,j 交换
           tmp = strs[i];
           strs[i] = strs[j];
           strs[j] = tmp;
       }
       //跳出循环后，交换i 和 l的位置，这样l第一次完成遍历，进行下一轮
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs,l,i - 1);
        quickSort(strs,i + 1,r);
    }

    /**
     * 快速排序
     * @param nums
     * @param start
     * @param end
     */
    public void quickSort1(int[] nums,int start,int end){
        if(start >= end){
            return;
        }
        int l = start + 1;
        int r = end;
        int pivot = nums[start];
        while (l <= r){
            if(nums[l] < pivot){
                l++;
                continue;
            }
            if(nums[r] >= pivot){
                r--;
                continue;
            }
            swap(nums,l,r);
        }
        swap(nums,start,r);
        quickSort1(nums,start, r - 1);
        quickSort1(nums,l,end);
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }


}
